package com.huawei.M01.iterator.july;

import java.util.Stack;

/**
 * 功能：接雨水,横着解决问题
 *
 * @author zhiwu
 * @Data 2023/7/11 23:22
 */
public class TrapWater {
    public int trap(int[] height) {
        int ans = 0;
        // 单调栈解决问题，第一步循环，第二步while，保证栈单调，第三步维持宽度，入栈
        Stack<Cent> stack = new Stack<>();
        for (int j : height) {
            // 记录维护水池的宽度
            int calculateWidth = 0;
            // 维持单调
            while (!stack.empty() && stack.peek().height <= j) {
                Cent singleCent = stack.pop();
                calculateWidth += singleCent.width;
                // 计算高度
                int singleHeight = singleCent.height;
                // 如果栈为空，说明已经不能存储水
                if (stack.empty()) {
                    continue;
                }

                int up = Math.min(stack.peek().height,j);
                if (up > singleHeight) {
                    ans += (up - singleHeight) * calculateWidth;
                }
            }
            stack.push(new Cent(calculateWidth + 1, j));
        }
        return ans;
    }

    private class Cent {
        private int width;
        private int height;

        public Cent(int width, int height) {
            this.width = width;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        System.out.println(new TrapWater().trap(new int[]{4, 2, 0, 3, 2, 5}));
    }
}
